{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "afa56065",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2025-08-03T07:31:04.355074Z",
     "iopub.status.busy": "2025-08-03T07:31:04.355074Z",
     "iopub.status.idle": "2025-08-03T07:31:08.934403Z",
     "shell.execute_reply": "2025-08-03T07:31:08.933402Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Grid World Environment:\n",
      "Shape: (3, 4)\n",
      "Actions: [0, 1, 2, 3]\n",
      "Start state: (2, 0)\n",
      "Goal state: (0, 3)\n",
      "Wall state: (1, 1)\n",
      "\n",
      "Running Monte Carlo First Visit...\n",
      "Episode 1000/5000 completed\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Episode 2000/5000 completed\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Episode 3000/5000 completed\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Episode 4000/5000 completed\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Episode 5000/5000 completed\n",
      "\n",
      "Value Function:\n",
      "State (0, 0): 0.110\n",
      "State (0, 1): 0.252\n",
      "State (0, 2): 0.384\n",
      "State (1, 0): -0.026\n",
      "State (1, 2): -0.452\n",
      "State (2, 0): -0.167\n",
      "State (2, 1): -0.329\n",
      "State (2, 2): -0.519\n",
      "State (2, 3): -0.776\n"
     ]
    },
    {
     "data": {
      "image/png": "iVBORw0KGgoAAAANSUhEUgAAApIAAAIQCAYAAAAy8I61AAAAOnRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjEwLjMsIGh0dHBzOi8vbWF0cGxvdGxpYi5vcmcvZiW1igAAAAlwSFlzAAAPYQAAD2EBqD+naQAAPjNJREFUeJzt3Qd4FOXaxvGHIqElofdeDCLSi0iXJnJoFhD4BAE7qIiKcvRQBA8cVESlHhVQAUFFqggCUkRASgAFAQHpLSSQQIIQCPtdz6u7J5sGecnuJpv/77pGslN2Z5Jx9p63TRaHw+EQAAAAIJWypnYDAAAAQBEkAQAAYIUgCQAAACsESQAAAFghSAIAAMAKQRIAAABWCJIAAACwQpAEAACAFYIkAAAArBAkgUzgsccek3Llyt1wvcOHD0uWLFlkxowZkt41b97cTDeyZs0ac0z6rzdlpN9leuCrvxOAW0OQBNKxQ4cOyYABA+T222+X3Llzm6lq1arSv39/+eWXX3yyT5s3bzZf+O+9916iZZ06dTLLpk+fnmhZ06ZNpWTJkpIedezY0fxuL168mOw6PXv2lBw5ckhERISkd8OHDzd/h6SmKVOm+HTfJk2aRLgG/Eh2X+8AgKQtWbJEunXrJtmzZzchpkaNGpI1a1bZu3evfPPNNzJ58mQTNMuWLXvD9/roo4/k+vXrabJftWvXNqFr/fr18uKLL7ot27Bhg9nfn376Sfr06eOaHxsbK1u2bJEOHTpIeqS/38WLF8v8+fOlV69eiZZfunRJFi5cKPfdd58ULFhQMgo9R/Lmzes2r0GDBuLrIFmoUCFTSp7wRuPPP/80YR1AxkGQBNKhgwcPyiOPPGJC4qpVq6R48eJuy//zn/+YL2QNlimJiYmRPHnyyG233ZZm+6ZBUcOIhsX49u3bJ+Hh4dKjRw8TMuPbtm2bXL58WRo3bnzLn6+hToNsWpdIBgYGyuzZs5MMkhoi9XepgTMjeeihh0xoywj0XM6ZM6evdwNAKlG1DaRDY8eONcFFq4gThkhnmHv++eeldOnSrnlawqOlTxpC77//fhOMnMEnqTaSkZGRZn5wcLDky5dPevfubebdDA2EZ86ckQMHDrjmabAMCgqSJ5980hUq4y9zbuekQfjOO++UgIAAKVGihKmuT/j52gayWrVqJohqiZUGyH/+85/J7tfx48elc+fOJjwXKVLElJheuXLlhseTK1cueeCBB0xoDwsLS7RcA6b+PjVwnjt3Tl5++WW56667zO9bj7ldu3ayc+dO63adSf19tAR5/Pjx5nekAato0aLy1FNPyfnz58WT7Td1vlaNJ6wm17+17qeeK3rOaImzhvqEZs6cKfXr1zd/q/z585u/2/fff2+W6THu3r1b1q5d66pqd/4+kmsj+dVXX0mdOnXM30hD8f/93//JiRMn3NZxnvs6X//++nPhwoXN3ykuLu6Wf18AkkeQBNJptXalSpVSXQ157do1adu2rQlR77zzjjz44INJrudwOEx7xs8//9x8MY8aNcqEMA2TN8MZCOOXPGpYvPvuu80+awmoVnPHX6ZBTKvnneFEg6MGyHfffdfs59SpU6VNmzZy9epVt8/SNoka1GrWrGmCVYsWLZLcJ60WbdmypSxfvty0K3399dflxx9/lMGDB9/UMWno1t/fl19+6TZfg6O+Z5cuXUyY+eOPP2TBggXyj3/8Q8aNGyevvPKK/Prrr9KsWTM5efKkpBUNjfrejRo1kvfff98Et1mzZpm/b8LfUXJ03zXQO6dbCaFdu3Y1bUhHjx5tftYQOmLECLd19PWjjz5q/v5vvvmmea03Oz/88INZrn+/UqVKSZUqVcy5p5P+nZKjn6GflS1bNvO5TzzxhGnWoedfwpsODYz6u9GmB3ru699Dz63//ve/1scM4CY4AKQrUVFRDv1fs3PnzomWnT9/3nH27FnXdOnSJdey3r17m+1ee+21RNvpsrJly7peL1iwwKw7duxY17xr1645mjRpYuZPnz49xX28cOGCI1u2bI5+/fq55oWEhDhGjBhhfq5fv77jlVdecS0rXLiwo3Xr1ubnsLAwR44cORxt2rRxxMXFudaZMGGC+exp06a55jVr1szMmzJlSqJ90GU6OY0fP96s++WXX7rmxcTEOCpVqmTmr169OsVj0uMvXry4o2HDhm7z9bN1++XLl5vXly9fdttvdejQIUdAQIDjzTffdJuX8HeZcJ+T+/v8+OOPZttZs2a5rbds2bIk5yc0bNgws17CyfkZSe2bk87X7RO+V9++fd3W69Kli6NgwYKu1/v373dkzZrVzE/4+7l+/brr5zvvvDPJ34H+feL/nWJjYx1FihRxVKtWzfHnn3+61luyZIlZb+jQoW6/P50X//evatWq5ahTp06KvysAt4YSSSCduXDhgvk3YScJpdWAWmXnnCZOnJhonWeeeeaGn7F06VJTPR5/XS31ee65525qH7V0sXr16q4SSS3t0urse+65x7zWUjRndfbvv/8uZ8+edZVirly50nS+GThwoFsbTy1t0mrib7/91u2ztOo7fsedlI5JmwFou0AnrV7Vqvabocev7VI3btxoqn7jV2trtbKWdjr3x7nfWgqmJab6twoJCZHQ0FBJC1qdq9XHrVu3ditR1Cpe/azVq1ff1PvMmzdPVqxY4Zq0RNPW008/7fa6SZMm5tid56uW0mp1/NChQxO13dUq69TaunWraWbw7LPPurWdbN++vSnRTHieJLePWoIMwHMIkkA6oyFNRUdHJ1qm1b8aCLQdWlI0HGrV4Y0cOXLEhK6EYVXD0M3SYOhsC6nV2BrEtGpbaaDUdo3aPjFh+0j97KQ+S3vrVqhQwbXcSYcMupmevLqdNgdIGFpSc0zONqUaHpVW92v1uAZMPT6lYUmHPqpcubIJldpuT0O9DscUFRUlaWH//v3mvbSJQvwbB530vEiqHWdStH1iq1atXJMGfFtlypRxe63tH5Wzulzb5mqA1OGp0kJy54nSIJnwPNGwqb+fhPuYFm1KASSPXttAOqMlURrydu3alWiZs81k/BKz+OKXlnmaBsMPP/zQBEUNks7OJ84gqSFSh/zRUksNuM6QmVraLtFbtMRPQ8oXX3xhOvXov1rbG7+39r///W/517/+JX379pWRI0dKgQIFzO9cS1hvNMSShty/ao/dJewQou+jITK5EsSEgSm1kishTKljijNIJ5TU8fhCcvsHwLMIkkA6pNV3H3/8sRn8W3vApjXnsEJauhW/VFJLGG9W/A43Wh0cv7RLO9HoZ2jI1KlWrVquIXuc417qZ2kJpJNWd+u4mFpyZntMGr412MQPSqk5JqWhUYOiljBqyaSWPNarV8+1/OuvvzYdfj755BO37bTzx42G2tESsqSqWhOWrlWsWNE0AdDfqSeCtLM0MWGHlYT7kRq6zxqAf/vtN9MxKjk3W80d/zy599573ZbpvJsZPxWA51G1DaRD2tNYg5eWeukwO2ldCqTDA2kPZR2wOn5plJYw3iwNi+XLlzeBVNuzOdtHOulrbTenX/rxh/3RoKhV1R988IHbcWgw0+pcDdG2x6S9pjXoOenwNKnttessfdS2fjt27Eg0dqSWfCX8/WubxoRD0iQXtnRAeW0z6qTDBiUck1N7KuvfQ0s8E9K/280O05QcbYuqoXfdunVu83VIJls67I6WzGpv7YQls/F/Xzo0083sf926dU2prD6JJ/4QTt99953s2bPH+jwBkLYokQTSIS0F09Kw7t27mzZizifb6BeyltrpMv3Svpn2kEnRJ8xoaddrr71mqsm1XZsOq5LaNn4aEHUIF5Ww/Z0GSa0adq4Xv1p2yJAhZmgYfVKMjs2oYVNDjJb86XBENrSzzoQJE8yA4to+U5sH6L6ldvByDce67zoIuUoYJHXYHw1L2gFI19Ohf7QKOn7panL0xkCHDNJhavr162faOmpQ0rEinZ1WlA5do8P/6JA3GmZ1WCQdUkfbTmpo1eGA4ncqsvH444/LmDFjzL8a2jRUascoW9o+VYfy0fCrnVx0XE5taqHNG/SmQ4/F2XxAb2B0yCndRsNiwhJHpcerA+/r71l/H/r/gt5U6bHreJQJn6oEwEdusdc3AA86cOCA45lnnjFD2OTMmdORK1cuR5UqVRxPP/20Y8eOHW7r6hAoefLkSfJ9Eg4voyIiIhyPPvqoIygoyBEcHGx+3r59+00N/+M0depUs37JkiUTLQsNDXUNO3PmzJlEy3W4Hz2W2267zVG0aFFznDq8UXw6TIwOF5OUpIbSOXLkiKNjx46O3LlzOwoVKuR44YUXXEPm3Gj4n/gmTpxottFhjBLS4X9eeuklM1SQ/j0aNWrk2LhxY6L9SW6InZkzZzoqVKhghkCqWbOmGVYoqb+P+u9//2uGr9HPCQwMdNx1112OwYMHO06ePJni/juH7NEhopKjQ0fp8E36t9f37tq1qxmaKbnhfxK+lx6XztfjjE+Hb9Jhd3Q4pPz585vfyYoVK1zLT58+7Wjfvr35TN3e+TtLOPyP09y5c13vV6BAAUfPnj0dx48fv6lz37nvADwni/7HVyEWAAAAGRdtJAEAAGCFIAkAAAArBEkAAAB4PkhqTzt9LJoOHaFTw4YNzVAMAAAAyHxS1dlm8eLFZgw1HZpEN/v000/l7bfflu3bt5vhKwAAAJB53HKvbX08mIZJHRMNAAAAmYf1gOT61AUdGDcmJsZUcSdHn0gQ/6kE+sSDc+fOScGCBW/6UVkAAADwHC1XvHjxonmAgD7wwmNBUp/ioMHx8uXL5hm98+fPN0/FSI4+zUCfYAEAAID07dixY6l6alqqq7ZjY2Pl6NGj5lFq+kzbjz/+WNauXZtsmExYIqnblSlTxjzmSjvuAJ6wZs0a82jB6Oho06YX8ATOM3jzPFsWvkzyl8/v692Bnzrz2xmZ8+ociYyMlODgYM+VSObIkcM8H9X5zFR9jqqGwqlTpya5vj5rVaeENEQ2b948tR8P3JQTJ06YZyzrl7s+RxjwBM4zePM8K1atmJSoWcLXuwM/lyWVzQ5veRxJbfMYv8QRAAAAmUOqSiSHDBki7dq1M1XT2iBz9uzZpsh9+fLlnttDAAAAZPwgGRYWJr169ZJTp06Z+nOtntYQ2bp1a8/tIQAAADJ+kPzkk088tycAAADIUHjWNgAAAKwQJAEAAGCFIAkAAAArBEkAAABYIUgCAADACkESAAAAVgiSAAAAsEKQBAAAgBWCJAAAAKwQJAEAAGCFIAkAAAArBEkAAABYIUgCAADACkESAAAAVgiSAAAAsEKQBAAAgBWCJAAAAKwQJAEAAGCFIAkAAAArBEkAAABYIUgCAADACkESAAAAVgiSAAAAsEKQBAAAgBWCJAAAAKwQJAEAAGCFIAkAAAArBEkAAABYIUgCAADACkESAAAAVgiSAAAAsEKQBAAAgBWCJAAAAKwQJAEAAGCFIAkAAAArBEkAAABYIUgCAADACkESAAAAVgiSAAAAsEKQBAAAgBWCJAAAAKwQJAEAAGCFIAkAAAArBEkAAABYIUgCAADACkESAAAAVgiSAAAAsEKQBAAAgBWCJAAAAKwQJAEAAGCFIAkAAAArBEkAAABYIUgCAADACkESAAAAVgiSAAAAsEKQBAAAgBWCJAAAAKwQJAEAAGCFIAkAAAArBEkAAABYyW63GQAAgOfFXY2TFeNWSOg3oZI1a1bJliOb5C+dX+579T4pdVcpOb3vtCwaukjO7D9j1i96e1Hp9GYn86+Tw+GQkbVGSsFyBaX/gv6u+RFHI+Ttpm/LmMNjfHJs/oAgCQAA0q3ZA2bLlZgrMnD5QMmdL7eZt2/NPgnbHyaBhQJlQocJ0uXfXaTOQ3XMsm3ztsmEjhPklbWvSFDRIDPv97W/S67gXHJy90mJOBIhBcsW9Okx+ROqtgEAQLp09uBZ+fXbX6X7h91dIVKFNA+R2g/UlvXT1kulRpVcIVLVebCOVGxYUdZ/st41b9PMTdKwV0Oz7OeZP3v9OPwZQRIAAKRLx385LoXKF5I8+fMkvXzncSlXr1yi+TpPl6mY8zGyd9Veqf1Qbbn70btl8xeb5fr16x7f98yCIOkDEydOlHLlyknOnDmlQYMGsnnz5mTX3b17tzz44INm/SxZssj48eMTrbNu3Trp0KGDlChRwqyzYMECDx8B/O08++ijj6RJkyaSP39+M7Vq1SrR+o899pg5v+JP9913nxeOBP5ynn3zzTdSt25dyZcvn+TJk0dq1qwpn3/+uds60dHRMmDAAClVqpTkypVLqlatKlOmTPHCkSAjCD8ULmObjpW36r8ls/vPvqlttn21Te5odYfkDs4tJe4sIYFFAk2wRNogSHrZ3LlzZdCgQTJs2DAJDQ2VGjVqSNu2bSUsLCzJ9S9duiQVKlSQMWPGSLFixZJcJyYmxryPXtABm/NszZo10r17d1m9erVs3LhRSpcuLW3atJETJ064rafB8dSpU67piy++8NIRwR/OswIFCsjrr79uzrFffvlF+vTpY6bly5e71tH3W7ZsmcycOVP27NkjAwcONMFy0aJFXjwypBelqpcy4fFS5CXzWksnB68bLK0GtpJLUZekVI1ScnjL4UTb6Tzd1lmtvf/H/TKixggzaRtJqrfTDkHSy8aNGydPPPGEuXg677Rz584t06ZNS3L9evXqydtvvy2PPPKIBAQEJLlOu3btZNSoUdKlSxcP7z389TybNWuWPPvss6aEqEqVKvLxxx+bqp9Vq1a5rafnoN7QOCctvUTmldrzrHnz5uY6dccdd0jFihXlhRdekOrVq8v69f9ry7Zhwwbp3bu3WVdLOp988kkTUFMq6YT/KlyxsFRrV03mPD/HBEen2Eux5t9GfRrJ/vX7ZdvX21zLtLPNgZ8OSKN+jeTYjmMSExEjI34bIcN2DjPTG6FvyN7VeyU6PNonx+RvCJJeFBsbK9u2bTPVhk46lIG+1jt0IL2cZ1oSfvXqVVOClLDkskiRIhISEiLPPPOMREREpPn+I3OcZzoci96o7Nu3T5o2beqaf88995jSRy0N13W0lPz33383JeTInHpM7CHF7ygu77V+T8Y0HCPvt3vf9MJu+XxLyVcinwxYNEC2zN1ihvcZWXukbJ27VQYsHiDBxYJNaWStLrXMuemkVdzaWUe3UVcuXpFhdw5zTe+1ec+HR5vxMPyPF4WHh0tcXJwULfq/sa2Uvt67l/YaSD/n2auvvmra3MYPCVqt/cADD0j58uXl4MGD8s9//tOUhmtoyJYtW5ofB/zzPIuKipKSJUvKlStXzHkzadIkad26tWv5hx9+aEohtY1k9uzZTQDQNrzxwyYyl+w5sku7Ie3MlBQNmU9/9XSSyx5+5+Ek5/f9rK/r5/ciCI63giAJwI22x50zZ44pfdQOFE7avMLprrvuMlWSWj2p67Vs2dJHe4uMJjAwUHbs2GE61WiJpLaJ1HbgWpXtDJKbNm0ypZJly5Y1nQn79++f6MYGQPpAkPSiQoUKmTvwM2f+Gn3fSV8n15EG8OZ59s4775gguXLlShMUU6Jf/vpZBw4cIEhmQrbnmZYwVqpUyfysbXK1Q83o0aNNkPzzzz9NSff8+fOlffv2Zh09DzV46rlJkATSH9pIelGOHDmkTp06bh0YnB0aGjZs6NN9g/+wPc/Gjh0rI0eOND1mdYiWGzl+/LhpI1m8ePE023dkvuuZbqPV3Erb5eoUvz2b0sDKuH9wDlA+vu14eaveW/Juy3fl1J5TSa636fNNMqruKNNmcs4Lc8xjFm9mGVKPEkkv02oc7ZGoX9T169c340Lq8D3a61H16tXLtB/SO3Rng/bffvvN9bM2QNe787x587ru6rWKSEuFnA4dOmTW0Y4SZcqU8clxImOdZ//5z39k6NChMnv2bNNT9vTp02a+nmc66Tk2YsQIM6apljZpG8nBgwebc1CHe0HmlNrzTP/VdbVJhIbHpUuXmnEkJ0+ebJYHBQVJs2bN5JVXXjFjSGrV9tq1a+Wzzz4zPcSBLwd9KQ17N5QGPRrIjoU7zOMTX1r1kts6OrzP0tFL5eXVL5sxIz/u+bFs+HSDNHm8SYrLYIcg6WXdunWTs2fPmi9t/bLWqh0tAXI2WD969Kjb3fjJkyelVq1artdavaOTXmy1bZraunWrtGjRwu3irvQCP2PGDC8eHTLqeaZf5Hqj8tBDD7m9j44POHz4cFMipOP+ffrppxIZGWnaq2kvWi3BTG5YKvi/1J5nGjJ1mCktzdagqENN6XiR+j5O2j53yJAh0rNnTzl37pwJk2+99ZY8/XTSnSmQeVw8e1GObj8qT8/761yo0bGGzHt1npz946wUrlDYtd7OhTul2n3VXM/Z1iGCVoxbYcJiSstghyDpAzq4rk5JcYZDJy0d0iEwUqJti260DjKf1Jxnhw8nHtA3Pv3Sjz9oNGBznul4tzqlREu8p0+fnqb7CP8QeSJSgooFSbbsf40SoU/Xyl8qv5w/ft4tSJ4/cV7yl/7fGLcFShcw69xoGezQRhIAAABWCJIAACDdy1cyn1w4fUHirv3VOUZr4rQ0UUsl48tfMr+cP/a/UsZzx8651klpGewQJAEAQLoXWDjQPFt765dbzeudi3aaJ9vEr9ZW1TtWl13LdsmFMxdM2Pxp+k9S+4HaN1wGO7SRBAAAGULXcV1ldv/ZsvK9lZIzMKd0n9DdzNdnceszuXUqVK6QtHu1nXmUoqrUqJLc89g95ueUlsEOQRIAAGQIRSsXlRe/fzHR/Ec++N+Tt5QOEaRTUlJahtSjahsAAABWCJIAAACwQpAEAACAFYIkAAAArBAkAQAAYIUgCQAAACsESQAAAFghSAIAAMAKQRIAAABWCJIAAACwQpAEAACAFYIkAAAArBAkAQAAYIUgCQAAACsESQAAAFghSAIAAMAKQRIAAABWCJIAAACwQpAEAACAFYIkAAAArBAkAQAAYIUgCQAAACsESQAAAFghSAIAAMAKQRIAAABWCJIAAACwQpAEAACAFYIkAAAArBAkAQAAYIUgCQAAACsESQAAAFghSAIAAMAKQRIAAABWCJIAAACwQpAEAACAFYIkAAAArBAkAQAAYIUgCQAAACsESQAAAFghSAIAAMAKQRIAAABWCJIAAACwQpAEAACAFYIkAAAArBAkAQAAYIUgCQAAACsESQAAAFghSAIAAMAKQRIAAABWCJIAAACwQpAEAACAFYIkAAAArBAkAQAAYIUgCQAAACsESQAAAFghSAIAAMAKQRIAAABWCJIAAACwQpAEAACAFYIkAAAArBAkAQAAYIUgCQAAACsESQAAAHg+SI4ePVrq1asngYGBUqRIEencubPs27fP7pMBAACQeYLk2rVrpX///rJp0yZZsWKFXL16Vdq0aSMxMTGe20MAAACkS9lTs/KyZcvcXs+YMcOUTG7btk2aNm2a1vsGAAAAfwmSCUVFRZl/CxQokOw6V65cMZPThQsXzL9r1qyREydO3MrHA8nasmWLtGjRQk6fPi27du3y9e7AT+m1LW/evLJy5Uqa+cDj17ODaw9K2IEwX+8O/NS5P85ZbZfF4XA4bDa8fv26dOzYUSIjI2X9+vXJrjd8+HAZMWJEovmzZ8+W3Llz23w0AAAA0tClS5ekR48eppAwKCjI8yWS2lZSS3pSCpFqyJAhMmjQILcSydKlS0t0dLRUrlzZ9uOBFGlJZFxcnCxatEh2797t692BnypZsqT06tXLXM9CQkJ8vTvwU1rifccdd0j4V19JxeBgX+8O/NSx8HCr7ayC5IABA2TJkiWybt06KVWqVIrrBgQEmCkhDZF169a1+XjghvQm5+DBgyZE/vzzz77eHfip6tWrm381RHI9g6c4m01oiKxVpIivdwd+KiY21vNBUmvBn3vuOZk/f75p41i+fHmrDwUAAEDGlz211dnatnHhwoVmLEmtPlTBwcGSK1cuT+0jAAAAMvo4kpMnTzaNMJs3by7Fixd3TXPnzvXcHgIAACBdSnXVNgAAAKB41jYAAACsECQBAABghSAJAAAAKwRJAAAAWCFIAgAAwApBEgAAAFYIkgAAALBCkAQAAIAVgiQAAACsECQBAABghSAJAAAAKwRJAAAAWCFIAgAAwApBEgAAAFYIkgAAALBCkAQAAIAVgiQAAACsECQBAABghSAJAAAAKwRJAAAAWCFIAgAAwApBEgAAAFYIkgAAALBCkAQAAIAVgiQAAACsECQBAABghSAJAAAAKwRJAAAAWCFIAgAAwApBEgAAAFYIkgAAALBCkAQAAIAVgiQAAACsECQBAABghSAJAAAAKwRJAAAAWCFIAgAAwApBEgAAAFYIkgAAALBCkAQAAIAVgiQAAACsECQBAABghSAJAAAAKwRJAAAAWCFIAgAAwApBEgAAAFYIkgAAALBCkAQAAIAVgiQAAACsECQBAABghSAJAAAAKwRJAAAAWCFIAgAAwApBEgAAAFYIkgAAALBCkAQAAIAVgiQAAACsECQBAABghSAJAAAAKwRJAAAAWMlutxkAAIBnNZ482fx7NS5O9kdESNUiRczryoUKyfBWraTWBx+YeY6/1x/asqW0vf121/YXr1yRKu+8I12qVZMJnTq55v946JA8PGuWVCpYUK47HBIUECDvtG8v1YoV8/IRZnwESQAAkC6tf+YZ8++R8+elyZQprtfOeXlz5HDNW7Zvnzz+9ddy+LXXJFvWvypc5+/aJTVKlJDFe/bImPvuk7wBAa7tNUQ6t52wYYP0X7hQ1j71lJePMOOjahsAAGR4zSpUkIuxsXL+zz9d8z7fvl0GNmok95QtK9/s3p3stq0qVZID4eFe2lP/QpAEAAAZ3sLffpOm5ctLoTx5zOu9YWFyIipKWlaqJI/WqiUzQ0OT3Xbe3yWXSD2CpA84HA4ZOnSoFC9eXHLlyiWtWrWS/fv333C7iRMnSrly5SRnzpzSoEED2bx5s9vyp556SipWrGjes3DhwtKpUyfZu3evB48EQGZnez1zGjNmjGTJkkUGDhzoNr958+Zmfvzp6aef9sARICOLjo017SirjRsnLy5eLP+691630shHatQw1dxtKleWI5GRsu/sWdfyAxERZlud9oeHy+TOnX10FBkbQdIHxo4dKx988IFMmTJFfv75Z8mTJ4+0bdtWLl++nOw2c+fOlUGDBsmwYcMkNDRUatSoYbYJCwtzrVOnTh2ZPn267NmzR5YvX24u8G3atJG4uDgvHRnSA/1S/+ijj1yvGzVqZM6FZs2aueZNnjxZ3nzzTfPzjBkzJCoqSnLnzu32PocOHTLnWUJ6jr3wwgsePQb49/XMacuWLTJ16lSpXr16ksufeOIJOXXqlGvSzwLic7aR/PXFF2Vg48bS9+uv5fLVq6ZzztydO+WLnTvlrvfeM51y/rx6VT6PVyrpbCOp04yuXaVs/vw+PZaMiiDpZfqFPn78eHnjjTdMiaFeQD/77DM5efKkLFiwINntxo0bZy6qffr0kapVq5qLtn7xT5s2zbXOk08+KU2bNjWllrVr15ZRo0bJsWPH5PDhw146OqQHq1evNqU5Ti1atJBNmzYlmvfDDz9IYGCgdOjQQXbu3CkPP/ywj/YYme16pqKjo6Vnz57mpid/Ml/geo0rVqyYawoKCvLQkSCj0xLrwc2aScHcueWTrVtl6b59Ui5/ftnz0ksmZOq04vHHZe4vv5iQibRDkPQyLeU5ffq0qf5xCg4ONlXVGzduTHKb2NhY2bZtm9s2WbNmNa+T2yYmJsaUHJUvX15Kly7tgSNBeqWhsUSJElKyZEnzWgOklj46g6R+IZcpU8acO927d5eVK1eaG5V+/fr5eM+RGa5nTv3795f27du7bZvQrFmzpFChQlKtWjUZMmSIXLp0KU33H/4XJke1bSvvr18vH2/eLA8nKOkOKVxYigcGynf79vlsH/0Rw/94mV50VdGiRd3m62vnsoTCw8NN9XRS2yRsAzlp0iQZPHiwCZIhISGyYsUKyZEjR5ofB9Kvq1evyoYNG0yp45dffmluJr777jtT/RgQEGDm65f8lStXTHjUqvBVq1aZ6u7bb79dfv/9d18fAvz4eqbmzJljmuho1XZyevToIWXLljU3Rb/88ou8+uqrsm/fPvnmm2/S8AiQUWi189EhQ244r3G5cvL7K68k+z7r4rWzjT+UEOxRIulhekedN29e16Rf8p6kVUXbt2+XtWvXmlDQtWvXm2qrBP+s3o7fKUtLKhs2bGjm63It5dEOEt9//71cu3ZNZs6cKX379vX1rsPPr2fa3Ebb2Op7acfB5GhTHW1redddd5nrmlaZz58/Xw4ePHiLRwEgLVEi6WEdO3Y0X+ZOWgqkzpw5Y77EnfR1zZo1k3wPrdrJli2bWSc+fa3VlPFptZJOlStXlrvvvtu0PdKLr1ZhIvPQoKiljUePHpU1a9aYeXpzoaWROj322GNmubaR/OOPP8zy2267zTSZeP311+mgBY9dz7SZjnYS1HbcTnq+rVu3TiZMmGDeU693CTk/98CBA2Z0CgDpA0HSw/SLWqf4jdM1/GlVovNCe+HCBdPb8Zlkitm1alp7ZOs2nf8enuD69evm9YABA5L9bP0snZwXe2QeWmVYpEgRU5KjX/7OILlkyRLzhb9161ZZuHChudnQ6kInLbXUdmuLFi3y4d7Dn69nLVu2lF9//dVtnnYirFKliqm+TipEqh07dph/4wdWZD4HIyLkmfnzJeLSJQnKmVMmde4sd/z92MT4PgsNlfHr15vHH+rYku+2by+3/X1upbQMqUfVtpc5x0vTHtX6Za0X1F69epl2QM6Q6LzY6t25kw79o70bP/30UzO8j16ktR2kXoCVliqNHj3a3O1rKZS2kdNeuDqu2/333++TY4XvaFX1+vXrzZe+Myjq2H76WudrD9sjR464hUil1Y3xO93oMFJaFemcnB14hg8f7jb/oYce8vIRIqNez/Qc1GYV8ScdMqhgwYLmZ6XV1yNHjjTXMx11Qt9b31dHpUhuqCBkDgMXL5bederItuefN0+seTaJ0QEOnz8v//7hB/muTx/Z/vzzEhYdLTO2bbvhMtihRNIHnJ1htA1QZGSkNG7cWJYtW+bWXkgvpNrJxqlbt25y9uxZ0zFCG7Hr3b9u42zkrtv++OOPZiiO8+fPm/l60dVAqSVTyHzatWuXaJ5+wTt99dVXiZZ/+OGHZlLaSScpevPivIEBbK5nN6K1MDqagF7P9L115IkHH3zQDDOEzOtsdLTsOHlS5j/6qHndsWpVeWXpUvkjIkIqFCzoWm/Rb79Ju5AQKfp36XnfunVl3I8/yhP166e4DHYIkj66i9fhWJwDQiclqbEftRo7uapsDQhLly5N0/0EAE9dz+JztuN10uCoTTGA+E5cuGACYPa/q6H13CsVHCzHoqLcgqS+Lp0vn+t1mXz55HhU1A2XwQ5V2wAAALBCkAQAAOleyaAgOXPxolz7e1QJ7eylpYmlg4Pd1tPXxyIjXa+PRkaakssbLYMdgiQAAEj3CufNK9WLFzePOVTa3rFEUJBbtbbqeMcd5uk1Gjo1bE7bulUe+LsjV0rLYIc2kgAAIEMY36GD6amtHWQCAwJk4t+jAzy3cKHpRHN/lSpSrkABGdKihbSdNs31tJs+deuan1NaBjsESQAAkCFULlRIVjz+eKL5H3bq5PZahwjSKSkpLUPqUbUNAAAAKwRJAAAAWCFIAgAAwApBEgAAAFYIkgAAALBCkAQAAIAVgiQAAACsECQBAABghSAJAAAAKwRJAAAAWCFIAgAAwApBEgAAAFYIkgAAALBCkAQAAIAVgiQAAACsECQBAABghSAJAAAAKwRJAAAAWCFIAgAAwApBEgAAAFYIkgAAALBCkAQAAIAVgiQAAACsECQBAABghSAJAAAAKwRJAAAAWCFIAgAAwApBEgAAAFYIkgAAALBCkAQAAIAVgiQAAACsECQBAABghSAJAAAAKwRJAAAAWCFIAgAAwApBEgAAAFYIkgAAALBCkAQAAIAVgiQAAACsECQBAABghSAJAAAAKwRJAAAAWCFIAgAAwApBEgAAAFYIkgAAALBCkAQAAIAVgiQAAACsECQBAABghSAJAAAAKwRJAAAAWCFIAgAAwApBEgAAAFYIkgAAALBCkAQAAIAVgiQAAACsECQBAABghSAJAAAAKwRJAAAAWCFIAgAAwApBEgAAAFYIkgAAALBCkAQAAIAVgiQAAAC8EyTXrVsnHTp0kBIlSkiWLFlkwYIFntkzAAAA+FeQjImJkRo1asjEiRM9s0cAAADIELKndoN27dqZCQAAAJlbqoNkal25csVMThcuXDD/rlmzRk6cOOHpj0cmdf78eSldurSULFlSqlev7uvdgZ8qWrSo+XflypWyb98+X+8O/NSWLVukRYsWsuboUTkQEeHr3YGfOhgZabVdFofD4bD9UG0jOX/+fOncuXOy6wwfPlxGjBiRaP7s2bMld+7cth8NAACANHLp0iXp0aOHREVFSVBQUPopkRwyZIgMGjTIrURSS4o2HT4lZUOqevrjkUnt2vSTdGpUV6KjoyUkJMTXuwM/pSWRd9xxB+cZPIrzDN6wfft2q+08HiQDAgLMlFDR0mWl3J01PP3xyKROHD5o/tWLbt26dX29O/BTzupszjN4EucZvEFvVGwwjiQAAAC8UyKpifXAgQOu14cOHZIdO3ZIgQIFpEyZMnZ7AQAAAP8Pklu3bjW9x5yc7R979+4tM2bMSNu9AwAAgP8EyebNm8stdPQGAACAn6CNJAAAAKwQJAEAAGCFIAkAAAArBEkAAABYIUgCAADACkESAAAAVgiSAAAAsEKQBAAAgBWCJAAAAKwQJAEAAGCFIAkAAAArBEkAAABYIUgCAADACkESAAAAVgiSAAAAsEKQBAAAgBWCJAAAAKwQJAEAAGCFIAkAAAArBEkAAABYIUgCAADACkESAAAAVgiSAAAAsEKQBAAAgBWCJAAAAKwQJAEAAGCFIAkAAAArBEkAAABYIUgCAADACkESAAAAVgiSAAAAsEKQBAAAgBWCJAAAAKwQJAEAAGCFIAkAAAArBEkAAABYIUgCAADACkESAAAAVgiSAAAAsEKQBAAAgBWCJAAAAKwQJAEAAGCFIAkAAAArBEkAAABYIUgCAADACkESAAAAVgiSAAAAsEKQBAAAgBWCJAAAAKwQJAEAAGCFIAkAAAArBEkAAABYIUgCAADACkESAAAAVgiSAAAAsEKQBAAAgBWCJAAAAKwQJAEAAGCFIAkAAAArBEkAAABYyW63GVJr0/dLZd6U9+X69TiJvXJFChQpJrcFBMj5sNNm+eG9v0mZylUka7askitPXhk1a4H8GR0tjzetKfe06yj93xrneq9dP2+Qt578PylRvoJcv+6QgJw5pe8/35Soc+Ey54O3zTqR4WflelycFChazLzu1O9ZadrhAR8dPQAA8EcESS84H3ZGpgx9RcbOWy5FSpYy8/7Y/YuUr3qXZMmSxbx+sEoJGTVrvuQJCnZt99N3C6VC1ery84rvpO8/R0quPHlcyzREvrtgpfl56cxpMvH1QfL+t2ul3r1tzby5H74jMRcvmIAJAADgCVRte0FkxFnJmi2bBAbnc82rcGd1V4hMzqqv50jnJ/pL1boNTKhMTvWGTeTsyeNpus8AAAA3QomkF5QNqSpVateXp1vWl6r17paQWnWlyT+6SMGixZPd5tiB3yX89Emp2bi5XI+7JvP/O0FaPdQjyXU3Ll8ije7v5MEjAAAASIwSSS/ImjWrDP7wY3nri4VSq3EL2Ru6RQb+o4WcOnIo2W1Wff2FNO/0kGTLlk1qN20pZ04ck+MH97uWnzz0h7zUuZX0a1xDvv3sY3nwqee9dDTIKBwOhwwdOlSKFy8uuXLlklatWsn+/f87h5IyefJkqV69ugQFBZmpYcOG8t1337mt89RTT0nFihXNexYuXFg6deoke/fu9fDRwJ/Os+HDh5samfhTlSpVXMvPnTsnzz33nISEhJj3LFOmjDz//PMSFRXlhSOCv5xn5cqVS3Se6dS/f3/XOqdPn5ZHH31UihUrJnny5JHatWvLvHnzvHBE/oMg6UWlKlSWNo88Kq9NnC6316gtW374Psn1rl29KmsXfS1rFnwlT99bX/q3uUdi//xTVn09O1Ebyamrt0qD1u1k/CsDzP9ogNPYsWPlgw8+kClTpsjPP/9sLpJt27aVy5cvJ7tNqVKlZMyYMbJt2zbZunWr3HvvvSYo7t6927VOnTp1ZPr06bJnzx5Zvny5Oe/atGkjcXFxXjoyZPTzTN15551y6tQp17R+/XrXspMnT5rpnXfekV27dsmMGTNk2bJl0q9fPy8cEfzlPNuyZYvbObZixQoz/+GHH3at06tXL9m3b58sWrRIfv31V3nggQeka9eusn37dq8clz8gSHpBxJlTsjd0s+t1dFSkhB0/KsXKlE1yfQ2YRUuXlY/WhcqUHzabafTcJbJ20TwTMuPLftttpkNNxOlTsnnlMo8fCzIGDXfjx4+XN954wwRBLWX87LPPzJfzggULkt2uQ4cOcv/990vlypXl9ttvl7feekvy5s0rmzZtcq3z5JNPStOmTc3dvt69jxo1So4dOyaHDx/20tEho59nKnv27KYUyDkVKlTItaxatWqmVEjPRy391hsaPRcXL14s165d88KRwR/OM60xiX+OLVmyxJxPzZo1c62zYcMGU/pdv359qVChgvmMfPnymZtp3ByCpBfEXYuTLye+JwPaNjbV0W/8Xxdp3rmr1G95X5Lrr5r3hTT9Rxe3eaUqVjZD+Wxd/dcdVXwBuXJLj4GvytwJ71IqCePQoUOmykarf5yCg4OlQYMGsnHjxpt6Dy1hnDNnjsTExJgq7qToMi2dLF++vJQuXTrN9h/+f55ptWSJEiXMl3fPnj3l6NGjKa6v1dra3EIDKDKXtLiexcbGysyZM6Vv375uHV3vuecemTt3rmlOcf36dXPN01LO5s2be+RY/BH/R3qBDvkz9JMvUlxn3t6Trp/f+O/MJNd555v/VYU7h/5xatGlq5mcuj338i3sMTI6veiqokWLus3X185lydHqHQ2OejHV0sj58+dL1apV3daZNGmSDB482ARJbcemVUY5cuTwwJHAH88zDQBaXa3njlY5jhgxQpo0aWKqsQMDAxOtHx4eLiNHjjSl4ch8buV65qQll5GRkfLYY4+5zf/yyy+lW7duUrBgQXOTkjt3bnPNq1SpUhoegX+jRBLwA7NmzTKhzzldTdAEIjX0y33Hjh2mHdIzzzwjvXv3lt9++81tHS1B0jZEa9euNVXg2qboRm3ikPGl1XnWrl07005Nqyi1ndvSpUvNl7x+qSd04cIFad++vbmZ0U468H9peT1z+uSTT8x5p6Xg8f3rX/8y597KlStNu/BBgwaZ65neUOPmUCIJ+IGOHTuaUh6nK1eumH/PnDljejk66euaNWum+F5asui8G9eONdpg/f3335epU6e6VSvppG0p7777bsmfP7+5i+/evbsHjg7+eJ7Fp23S9IbkwIEDbvMvXrwo9913nyml1PPrtttuS5PjQOY6z44cOWKC4jfffOM2/+DBgzJhwgRTEq6dv1SNGjXkxx9/lIkTJ5qOPbgxgqSPnTz8h0x47QW5cP685A4MlAGjx0uZyiGJ1gs7fkwmDBkoh/bskiKlSrtVbf8wb458+/nHrtfa8UbHqxz84SdeOw74ln7Rxq8S1Lay2rh81apVrgutluw4SxlTQ9sNOS/kSdHP0imldeAfPHWeRUdHmy91HYbFSd9HSysDAgJMj9qcOXOm8dEgs5xn2o67SJEipmQ7vkuXLrmG6ItPh93T6x5uDlXbPjZ12KvSquv/yYTl66XL4/1NWExKrrx5pfvAwTLwnYmJlt374CMmWDqnfIWLSJN/8FztzEwbkw8cOND0qHYOa6HDXGi1TufOnV3rtWzZ0tyROw0ZMkTWrVtnemDrNvp6zZo1pipb/fHHHzJ69GjTo1E7R2iPR62i1HHdtLc3Mhfb8+zll182zSL0PNNzqEuXLubL21mirSFBh5TSNrhaJamvtS2cTgwzlfnYnmdKA6EGSW2ik7Cjlo5dqrUvOjbu5s2bzc3Mu+++a9p8x39fpIwSSR+KigiXg7t2ujri3N22vXw86nUzUHnxsuXd1g3Ml1/uqNNAdv28IcX3/H1nqHnfeve28ei+I/1zdobRDgraBqhx48ZmLL74JTt64dSODE5hYWHmAq0dILTqWtuw6ViRrVu3Nst1W6320aE4zp8/bxq761BAGgb0jh+Zj815dvz4cRMaIyIizBAtuo0OMaU/q9DQUFPapBJ2etAevDr0FDIXm/NMaZW23vRqb+2EtKmEts997bXXzFBTWjKu59unn37KjXEqECR9KPzUSclfuIhk+/suSe+6ChUvKeGnTiQKkjdLn4jTrONDZnxJZG56Pr355ptmSk7CsR+19CclWgKgF17gVs4zHWIlJTr0CkOZ4VbPM6Ul2ymdS9rOmyfZ3Bqqtv3I5UuX5KelC6XlQ3R4AAAAnkeJpJfpYw8Xz/ir92vj9p3l/Nkwibt2zZRK6l2TlkZqqaSNDcsWS+lKIVK60u1pvNcAAACJESS9rHnnh83ktH3davPow3sf6Cabln8rBYsWt67W/mHeF9LyoUfScG8BAACSR9W2jz014j+yYu5M8/jE+R9NkP7/fs+1bNIbL8mWH5abn6/8eUmeaFZH3h34pBw/uN/8PPPdf7vWPfHHATm0Z7c0atfJJ8cBAAAyH0okfaxkhUoyeu7iJJc9O+pdt+dpf7R2W4rvMyt0v0f2EQAAICmUSAIAAMAKQRIAAABWCJIAAACwQpAEAACAFYIkAAAArBAkAQAAYIUgCQAAACsESQAAAFghSAIAAMAKQRIAAABWCJIAAACwQpAEAACAFYIkAAAArBAkAQAAYIUgCQAAACsESQAAAFghSAIAAMAKQRIAAABWCJIAAACwQpAEAACAFYIkAAAArBAkAQAAYIUgCQAAACsESQAAAFghSAIAAMAKQRIAAABWCJIAAACwQpAEAACAFYIkAAAArBAkAQAAYIUgCQAAACsESQAAAFghSAIAAMAKQRIAAABWCJIAAACwQpAEAACAFYIkAAAArBAkAQAAYIUgCQAAACsESQAAAFghSAIAAMAKQRIAAABWCJIAAACwQpAEAACAFYIkAAAArBAkAQAAYIUgCQAAACsESQAAAFghSAIAAMAKQRIAAABWCJIAAACwQpAEAACAFYIkAAAArBAkAQAAYIUgCQAAACsESQAAAFghSAIAAMAKQRIAAABWCJIAAACwQpAEAACAFYIkAAAArBAkAQAAYIUgCQAAAO8FyYkTJ0q5cuUkZ86c0qBBA9m8ebPdpwMAACDzBMm5c+fKoEGDZNiwYRIaGio1atSQtm3bSlhYmGf2EAAAAP4RJMeNGydPPPGE9OnTR6pWrSpTpkyR3Llzy7Rp0zyzhwAAAEiXsqdm5djYWNm2bZsMGTLENS9r1qzSqlUr2bhxY5LbXLlyxUxOUVFR5t+j+/fZ7zVwA2eOHJFLxQvI9u3bJTo62te7Az+1f/9+CQkJ4TyDR3GewRt++eUX86/D4fBckAwPD5e4uDgpWrSo23x9vXfv3iS3GT16tIwYMSLR/Klvvp6qHQVSa9YHvt4DAAAyloiICAkODvZMkLShpZfaptIpMjJSypYtK0ePHk3VjgKpceHCBSldurQcO3ZMgoKCfL078FOcZ/AGzjN4g9YYlylTRgoUKJCq7VIVJAsVKiTZsmWTM2fOuM3X18WKFUtym4CAADMlpCGS/yHgaXqOcZ7B0zjP4A2cZ/AGbbKYqvVTs3KOHDmkTp06smrVKte869evm9cNGzZM1QcDAAAgY0t11bZWU/fu3Vvq1q0r9evXl/Hjx0tMTIzpxQ0AAIDMI9VBslu3bnL27FkZOnSonD59WmrWrCnLli1L1AEnOVrNrWNQJlXdDaQVzjN4A+cZvIHzDOn5PMviSG0/bwAAAIBnbQMAAMAWQRIAAABWCJIAAACwQpAEAABA+g+SEydOlHLlyknOnDmlQYMGsnnzZm9+PDKBdevWSYcOHaREiRKSJUsWWbBgga93CX5GH/tar149CQwMlCJFikjnzp1l3759vt4t+JnJkydL9erVXYOQ61jN3333na93C35uzJgx5rtz4MCB6S9Izp0714xBqV3LQ0NDpUaNGtK2bVsJCwvz1i4gE9AxTfXc0psWwBPWrl0r/fv3l02bNsmKFSvk6tWr0qZNG3PuAWmlVKlS5kt927ZtsnXrVrn33nulU6dOsnv3bl/vGvzUli1bZOrUqeYGJl0O/6MlkHoXP2HCBNcTcfTZoc8995y89tpr3tgFZDJ6VzV//nxTYgR4io6rqyWTGjCbNm3q692BH9NnIL/99tvSr18/X+8K/Ex0dLTUrl1bJk2aJKNGjTJjhOsDZ9JNiWRsbKy5q2rVqtX/PjhrVvN648aN3tgFAPCIqKgo15c84AlxcXEyZ84cU+rN44jhCVrL0r59e7ec5rEn29gIDw83/yMkfPqNvt67d683dgEA0pzWrGhbokaNGkm1atV8vTvwM7/++qsJjpcvX5a8efOaGpaqVav6erfgZ+bMmWOaHGrVtg2vBEkA8Ne7+F27dsn69et9vSvwQyEhIbJjxw5T6v31119L7969TRMKwiTSyrFjx+SFF14w7b21I3S6DZKFChWSbNmyyZkzZ9zm6+tixYp5YxcAIE0NGDBAlixZYkYK0I4RQFrLkSOHVKpUyfxcp04dU2L0/vvvmw4RQFrQZofa6VnbRzppDbJe17RPy5UrV0x+83kbSf2fQf8nWLVqlVuVkL6mvQeAjET7J2qI1GrGH374QcqXL+/rXUImod+b+sUOpJWWLVuaJhRa8u2c6tatKz179jQ/3yhEerVqW4f+0WJ53cH69eub3kDacLhPnz7e2gVkkp5nBw4ccL0+dOiQ+Z9BO0KUKVPGp/sG/6nOnj17tixcuNCMJXn69GkzPzg4WHLlyuXr3YOfGDJkiLRr185cty5evGjOuTVr1sjy5ct9vWvwI4GBgYnad+fJk0cKFix40+2+vRYku3XrZobJGDp0qLnwatfyZcuWJeqAA9wKHW+tRYsWbjcwSm9iZsyY4cM9gz8NFK2aN2/uNn/69Ony2GOP+Wiv4G+0urFXr15y6tQpc5OiY/tpiGzdurWvdw3wzTiSAAAA8C88axsAAABWCJIAAACwQpAEAACAFYIkAAAArBAkAQAAYIUgCQAAACsESQAAAFghSAIAAMAKQRIAAABWCJIAAACwQpAEAACAFYIkAAAAxMb/A6EKT+5J95qYAAAAAElFTkSuQmCC",
      "text/plain": [
       "<Figure size 800x600 with 1 Axes>"
      ]
     },
     "metadata": {},
     "output_type": "display_data"
    }
   ],
   "source": [
    "import numpy as np\n",
    "import matplotlib.pyplot as plt\n",
    "import random\n",
    "from collections import defaultdict\n",
    "\n",
    "class GridWorld:\n",
    "    def __init__(self):\n",
    "        self.action_space = [0, 1, 2, 3]\n",
    "        self.action_meaning = {0: 'up', 1: 'right', 2: 'down', 3: 'left'}\n",
    "        self.reward_map=np.array(\n",
    "            [[0,0,0,1.0],\n",
    "             [0,None,0,-1.0],\n",
    "             [0,0,0,0]]\n",
    "        )\n",
    "        self.goal_state=(0,3)\n",
    "        self.wall_state=(1,1)\n",
    "        self.start_state=(2,0)\n",
    "        self.agent_state=self.start_state\n",
    "    \n",
    "    @property\n",
    "    def height(self):\n",
    "        return self.reward_map.shape[0]\n",
    "    \n",
    "    @property\n",
    "    def width(self):\n",
    "        return self.reward_map.shape[1]\n",
    "\n",
    "    @property\n",
    "    def shape(self):\n",
    "        return self.reward_map.shape\n",
    "\n",
    "    @property\n",
    "    def actions(self):\n",
    "        return self.action_space\n",
    "\n",
    "    @property\n",
    "    def states(self):\n",
    "        for i in range(self.height):\n",
    "            for j in range(self.width):\n",
    "                if (i, j) != self.wall_state:  # 排除墙壁状态\n",
    "                    yield (i, j)\n",
    "\n",
    "    def next_state(self, state, action):\n",
    "        # 根据当前状态和动作计算下一个状态的位置\n",
    "        action_move_map = [(-1, 0), (0, 1), (1, 0), (0, -1)]\n",
    "        move=action_move_map[action]\n",
    "        next_state=(state[0]+move[0],state[1]+move[1])\n",
    "        ny,nx=next_state\n",
    "        if ny<0 or ny>=self.height or nx<0 or nx>=self.width:\n",
    "            next_state=state\n",
    "        elif (ny,nx)==self.wall_state:\n",
    "            next_state=state\n",
    "        return next_state\n",
    "    \n",
    "    def reward(self, state, action, next_state):\n",
    "        return self.reward_map[next_state]\n",
    "    \n",
    "    def is_terminal(self, state):\n",
    "        return state == self.goal_state or state == (1, 3)  # 目标状态或负奖励状态\n",
    "    \n",
    "    def reset(self):\n",
    "        self.agent_state = self.start_state\n",
    "        return self.agent_state\n",
    "    \n",
    "    def step(self, action):\n",
    "        current_state = self.agent_state\n",
    "        next_state = self.next_state(current_state, action)\n",
    "        reward = self.reward(current_state, action, next_state)\n",
    "        self.agent_state = next_state\n",
    "        done = self.is_terminal(next_state)\n",
    "        return next_state, reward, done\n",
    "    \n",
    "    def render_v(self, value_function=None):\n",
    "        \"\"\"可视化价值函数\"\"\"\n",
    "        if value_function is None:\n",
    "            value_function = {}\n",
    "        \n",
    "        fig, ax = plt.subplots(figsize=(8, 6))\n",
    "        \n",
    "        # 创建网格显示\n",
    "        for i in range(self.height):\n",
    "            for j in range(self.width):\n",
    "                if (i, j) == self.wall_state:\n",
    "                    # 墙壁用黑色表示\n",
    "                    ax.add_patch(plt.Rectangle((j, self.height-1-i), 1, 1, \n",
    "                                             facecolor='black', edgecolor='white'))\n",
    "                    ax.text(j+0.5, self.height-1-i+0.5, 'WALL', \n",
    "                           ha='center', va='center', color='white', fontsize=8)\n",
    "                elif (i, j) == self.goal_state:\n",
    "                    # 目标状态用绿色表示\n",
    "                    ax.add_patch(plt.Rectangle((j, self.height-1-i), 1, 1, \n",
    "                                             facecolor='lightgreen', edgecolor='black'))\n",
    "                    value = value_function.get((i, j), 0)\n",
    "                    ax.text(j+0.5, self.height-1-i+0.5, f'GOAL\\n{value:.2f}', \n",
    "                           ha='center', va='center', fontsize=8)\n",
    "                elif (i, j) == (1, 3):  # 负奖励状态\n",
    "                    ax.add_patch(plt.Rectangle((j, self.height-1-i), 1, 1, \n",
    "                                             facecolor='lightcoral', edgecolor='black'))\n",
    "                    value = value_function.get((i, j), 0)\n",
    "                    ax.text(j+0.5, self.height-1-i+0.5, f'TRAP\\n{value:.2f}', \n",
    "                           ha='center', va='center', fontsize=8)\n",
    "                elif (i, j) == self.start_state:\n",
    "                    # 起始状态用蓝色表示\n",
    "                    ax.add_patch(plt.Rectangle((j, self.height-1-i), 1, 1, \n",
    "                                             facecolor='lightblue', edgecolor='black'))\n",
    "                    value = value_function.get((i, j), 0)\n",
    "                    ax.text(j+0.5, self.height-1-i+0.5, f'START\\n{value:.2f}', \n",
    "                           ha='center', va='center', fontsize=8)\n",
    "                else:\n",
    "                    # 普通状态用白色表示\n",
    "                    ax.add_patch(plt.Rectangle((j, self.height-1-i), 1, 1, \n",
    "                                             facecolor='white', edgecolor='black'))\n",
    "                    value = value_function.get((i, j), 0)\n",
    "                    ax.text(j+0.5, self.height-1-i+0.5, f'{value:.2f}', \n",
    "                           ha='center', va='center', fontsize=10)\n",
    "        \n",
    "        ax.set_xlim(0, self.width)\n",
    "        ax.set_ylim(0, self.height)\n",
    "        ax.set_aspect('equal')\n",
    "        ax.set_title('Grid World Value Function')\n",
    "        ax.set_xticks(range(self.width+1))\n",
    "        ax.set_yticks(range(self.height+1))\n",
    "        plt.grid(True)\n",
    "        plt.show()\n",
    "\n",
    "# 蒙特卡洛方法实现\n",
    "def random_policy(env, state):\n",
    "    \"\"\"随机策略\"\"\"\n",
    "    return random.choice(env.actions)\n",
    "\n",
    "def epsilon_greedy_policy(env, state, Q, epsilon=0.1):\n",
    "    \"\"\"ε-贪婪策略\"\"\"\n",
    "    if random.random() < epsilon:\n",
    "        return random.choice(env.actions)\n",
    "    else:\n",
    "        # 选择Q值最大的动作\n",
    "        q_values = [Q.get((state, action), 0) for action in env.actions]\n",
    "        max_q = max(q_values)\n",
    "        best_actions = [action for action, q in zip(env.actions, q_values) if q == max_q]\n",
    "        return random.choice(best_actions)\n",
    "\n",
    "def generate_episode(env, policy, Q=None, epsilon=0.1):\n",
    "    \"\"\"生成一个episode\"\"\"\n",
    "    episode = []\n",
    "    state = env.reset()\n",
    "    \n",
    "    while True:\n",
    "        if Q is not None:\n",
    "            action = epsilon_greedy_policy(env, state, Q, epsilon)\n",
    "        else:\n",
    "            action = policy(env, state)\n",
    "        \n",
    "        next_state, reward, done = env.step(action)\n",
    "        episode.append((state, action, reward))\n",
    "        \n",
    "        if done:\n",
    "            break\n",
    "        state = next_state\n",
    "    \n",
    "    return episode\n",
    "\n",
    "def monte_carlo_first_visit(env, num_episodes=10000, gamma=0.9):\n",
    "    \"\"\"首次访问蒙特卡洛方法\"\"\"\n",
    "    returns = defaultdict(list)\n",
    "    value_function = defaultdict(float)\n",
    "    \n",
    "    for episode_num in range(num_episodes):\n",
    "        # 生成episode\n",
    "        episode = generate_episode(env, random_policy)\n",
    "        \n",
    "        # 计算每个状态的回报\n",
    "        G = 0\n",
    "        visited_states = set()\n",
    "        \n",
    "        # 从后往前计算回报\n",
    "        for t in reversed(range(len(episode))):\n",
    "            state, action, reward = episode[t]\n",
    "            G = gamma * G + reward\n",
    "            \n",
    "            # 首次访问\n",
    "            if state not in visited_states:\n",
    "                visited_states.add(state)\n",
    "                returns[state].append(G)\n",
    "                value_function[state] = np.mean(returns[state])\n",
    "        \n",
    "        # 每1000个episode打印一次进度\n",
    "        if (episode_num + 1) % 1000 == 0:\n",
    "            print(f\"Episode {episode_num + 1}/{num_episodes} completed\")\n",
    "    \n",
    "    return dict(value_function)\n",
    "\n",
    "def monte_carlo_control(env, num_episodes=10000, gamma=0.9, epsilon=0.1):\n",
    "    \"\"\"蒙特卡洛控制方法\"\"\"\n",
    "    Q = defaultdict(float)\n",
    "    returns = defaultdict(list)\n",
    "    \n",
    "    for episode_num in range(num_episodes):\n",
    "        # 生成episode\n",
    "        episode = generate_episode(env, None, Q, epsilon)\n",
    "        \n",
    "        # 计算每个状态-动作对的回报\n",
    "        G = 0\n",
    "        visited_pairs = set()\n",
    "        \n",
    "        # 从后往前计算回报\n",
    "        for t in reversed(range(len(episode))):\n",
    "            state, action, reward = episode[t]\n",
    "            G = gamma * G + reward\n",
    "            \n",
    "            # 首次访问\n",
    "            state_action = (state, action)\n",
    "            if state_action not in visited_pairs:\n",
    "                visited_pairs.add(state_action)\n",
    "                returns[state_action].append(G)\n",
    "                Q[state_action] = np.mean(returns[state_action])\n",
    "        \n",
    "        # 每1000个episode打印一次进度\n",
    "        if (episode_num + 1) % 1000 == 0:\n",
    "            print(f\"Episode {episode_num + 1}/{num_episodes} completed\")\n",
    "    \n",
    "    # 从Q函数计算价值函数\n",
    "    value_function = {}\n",
    "    for state in env.states:\n",
    "        q_values = [Q.get((state, action), 0) for action in env.actions]\n",
    "        value_function[state] = max(q_values) if q_values else 0\n",
    "    \n",
    "    return dict(value_function), dict(Q)\n",
    "\n",
    "# 测试代码\n",
    "env = GridWorld()\n",
    "print(\"Grid World Environment:\")\n",
    "print(f\"Shape: {env.shape}\")\n",
    "print(f\"Actions: {env.actions}\")\n",
    "print(f\"Start state: {env.start_state}\")\n",
    "print(f\"Goal state: {env.goal_state}\")\n",
    "print(f\"Wall state: {env.wall_state}\")\n",
    "\n",
    "# 使用蒙特卡洛方法计算价值函数\n",
    "print(\"\\nRunning Monte Carlo First Visit...\")\n",
    "value_function = monte_carlo_first_visit(env, num_episodes=5000)\n",
    "\n",
    "print(\"\\nValue Function:\")\n",
    "for state in sorted(value_function.keys()):\n",
    "    print(f\"State {state}: {value_function[state]:.3f}\")\n",
    "\n",
    "# 可视化价值函数\n",
    "env.render_v(value_function)\n"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.12.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
